1. Field of the Invention
The invention relates to a method for performing discrete cosine transform (DCT) and its inverse, more particularly to a method for performing two-dimensional DCT/IDCT involving a reduced number of multiplication operations.
2. Description of the Related Art
U.S. Pat. No. 5,471,412 by the applicant discloses a discrete cosine transform (DCT) and an inverse discrete cosine transform (IDCT) method and apparatus that use six-stage DCT/IDCT fast algorithms to process a sequence of input data of an 8.times.8 data block. The six stages of the DCT/IDCT fast algorithms generally consist of interleaved butterfly operation stages and multiplication operation stages. The multiplication operation stages include intrinsic multiplication operations, post-addition multiplication operations, and post-multiplication subtraction operations. In the aforementioned U.S. Patent, the entire disclosure of which is incorporated herein by reference, a single butterfly operation unit performs the butterfly operation stages, while a single multiplication operation unit performs the multiplication operation stages. The butterfly operation unit and the multiplication operation unit operate in a recycling and parallel processing manner so that DCT and IDCT can be achieved efficiently with a relatively inexpensive hardware cost.
FIGS. 1 and 3 respectively illustrate flow graphs of the six-stage DCT and IDCT fast algorithms employed in the aforesaid U.S. patent. The DCT fast algorithm uses three kinds of arithmetic operations: butterfly, intrinsic multiplication, and post-addition multiplication, as shown in FIGS. 2A to 2C. The IDCT fast algorithm also uses three kinds of arithmetic operations: butterfly, intrinsic multiplication, and post-multiplication subtraction, as shown in FIGS. 2A, 2B and 2D.
Referring again to FIG. 1, the six stages of the DCT fast algorithm include a first stage involving four butterfly operations, a second stage involving two post-addition multiplication operations, a third stage involving four butterfly operations, a fourth stage involving three post-addition multiplication operations, a fifth stage involving four butterfly operations, and a sixth stage involving eight intrinsic multiplication operations.
Referring to FIG. 3, the six stages of the IDCT fast algorithm include a first stage involving eight intrinsic multiplication operations, a second stage involving four butterfly operations, a third stage involving three post-multiplication subtraction operations, a fourth stage involving four butterfly operations, a fifth stage involving two post-multiplication subtraction operations, and a sixth stage involving four butterfly operations.
In general, multiplication operations for DCT/IDCT are relatively time-consuming and require relatively complex hardware. Although the aforementioned U.S. Patent employs a fast algorithm that involves only thirteen multiplication operations for one-dimensional transformation, or a total number of 208 (2.times.8.times.13) multiplication operations for two-dimensional transformation of an 8.times.8 data block, it is desirable to further reduce the number of multiplication operations in order to achieve a higher processing speed.